package com.gitee.feizns.explore.data_structure.tree.bs.easy;

/**
 * @author feizns
 * @since 2019/12/9
 */
public class HasPathSum {

    public static void main(String[] args) {
        System.out.println(hasPathSum(create(), 1));
    }

    private static TreeNode create() {
        TreeNode ret = new TreeNode(1);
        ret.left = new TreeNode(2);
        return ret;
    }

    public static boolean hasPathSum(TreeNode root, int sum) {
        if ( root != null ) {
            sum -= root.val;
            if ( root.left == null && root.right == null )
                return sum == 0;
            return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
        }
        return false;
    }

//    public static boolean hasPathSum(TreeNode root, int sum) {
//        return hasPathSum(root, 0, sum);
//    }

    private static boolean hasPathSum(TreeNode root, int curt, int sum) {
        if ( root != null ) {
            curt += root.val;
            if ( root.left == null && root.right == null && curt == sum )
                return true;
            else
                return hasPathSum(root.left, curt, sum) || hasPathSum(root.right, curt, sum);
        }
        return false;
    }

}
